COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	(defun quicksort (a)
C00004 ENDMK
C⊗;
(defun quicksort (a)
 (labels ((quicksort (m n)
           (cond ((not (< m n)))
		 (t (let ((d (aref a m)))
		     (let ((i (partition a m n d)))
	              (setf (aref a i) d)
		      (quicksort m (1- i))
		      (quicksort (1+ i) n)
		      t))))))
  (quicksort 0 (1- (length a)))))

(defun partition (a m n d)
 (labels ((down (i j d)
           (let ((k (findb i j d)))
            (setf (aref a i) (aref a k))
	    (up (1+ i) k d)))
	  (up (i j d)
           (let ((k (findf i j d)))
	    (setf (aref a j) (aref a k))
	    (down k (1- j) d)))
	  (findb (i j d)
           (cond ((= i j)
		  (return-from partition i))
		 ((< (aref a j) d)
		  j)
		 (t (findb i (1- j) d))))
	  (findf (i j d)
		 (cond ((= i j)
			(return-from partition i))
		       ((> (aref a i) d)
			i)
		       (t (findf (1+ i) j d)))))
	 (down m n d)))

(defvar *a*)

(defun init-array (n)
 (setq *a* (make-array (list n)))
 (dotimes (i n) (setf (aref *a* i) (random 200))))

(defun init-only-array (a)
 (dotimes (i (length a)) (setf (aref a i) (random 200))))